package xio.leetcode.java;

import java.util.HashMap;

/**
 * 128. Longest Consecutive Sequence (Hard)
 * 给定一个未排序的整数数组，找出最长连续序列的长度。
 * <p>
 * 要求算法的时间复杂度为 O(n)。
 * <p>
 * 示例:
 * <p>
 * 输入: [100, 4, 200, 1, 3, 2]
 * 输出: 4
 * 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
 * <p>
 * 思路：要求时间复杂度为O(n),可以使用查找仅需O(1)的哈希表。
 * 利用一个HashMap保存各个候选最长序列的左右边界及其长度, 例如{100, 4, 200, 1, 3, 2}中数字1和4对应的长度都是4
 * 依次遍历每个数num, 如果map中存在num-1或num+1则更新num所处的序列长度及其边界值
 */
public class LC128_LongestConsecutive {
    public int longestConsecutive(int[] nums) {
        int max = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            // 重复出现的数直接忽略
            if (map.containsKey(num)) {
                continue;
            }
            // 左边界目前长度
            int left = map.getOrDefault(num - 1, 0);
            // 右边界目前长度
            int right = map.getOrDefault(num + 1, 0);
            // 再加上这个数的长度(1)
            int range = left + right + 1;
            // 更新最大长度
            max = Math.max(max, range);
            // 更新这个序列左右边界的长度值
            map.put(num - left, range);
            map.put(num + right, range);
            map.put(num, range);
        }
        return max;
    }

    public static void main(String[] args) {
        LC128_LongestConsecutive lc = new LC128_LongestConsecutive();
        System.out.println(lc.longestConsecutive(new int[]{1, 2, 0, 1}));
    }
}
